⭐️ 9.9. Dynamic Memory Allocation


32bit word (4 byte)를 기준으로 챕터가 진행된다. double word로 정렬한다는 것은 곧 모든 객체의 주소가 8의 배수가 된다는 것을 의미한다.

동적 메모리 할당자(dynamic memory allocator)로 힙 영역의 메모리를 어떻게 하면 편하게 할당하고 해제할 수 있을지에 대한 고민이 malloc의 구현에 영향을 주었다. 동적 메모리 할당 덕분에 우리는 mmap과 같은 낮은 수준의 메모리 관리로부터 벗어나게 되었다.

DUMP

9.9.1. The malloc and free functions

9.9.2. Why Dynamic Memory Allocation?

9.9.3. Allocator Requirenments and Goals

Allocator의 제약조건

Allocator의 달성수준

9.9.4. Fragmentation

Throughput에만 신경을 쓴다면 사실 free한 공간을 다시 재활용 하지 않아도 된다. 이 경우 두 가지 파편화가 발생할 수 있다.

  1. Internal Fragmentation payload(실제로 필요한 용량)보다 할당해준 용량이 더 많은 경우, "고봉밥 할머니 style"
  2. External Fragmentation 구멍의 총합은 큰데 너무 자잘해서 요청을 받아줄 수 없는 경우 → 휴리스틱 기법을 사용해 external frag를 줄이려고 노력한다. 어떻게? 작은 구멍의 크기보다는 큰 구멍의 크기를 유지하는 방향으로

9.9.5. Implementation Issues

결국 throughput과 mem utilization 모두 챙겨야 하는데, 참고할 만한 기준이 있을까?

9.9.6. Implicit Free Lists

블럭의 첫번째 워드(head)(4byte)에 블럭에 대한 메타데이터를 저장한다. 별 건 아니고 블럭의 사이즈 (payload + padding)와 할당여부에 대한 정보를 담는다.

두 필드를 하나의 워드에 담을 수 있는게, 블럭 사이즈는 정렬 때문에 항상 8의 배수이기 때문이다. 따라서 앞의 3자리는 언제나 0인데, 0번째 비트 (LSB)를 0으로 만들면 Free, 1로 만들면 Allocated로 정의한다.

모든 블럭에는 헤더가 있으니까 헤더 정보를 보고 모든 블럭을 순회할 수 있긴 함. while (*cur & ~7) { cur += sizeof(void *) * (*cur & ~7); } 루프를 돌면서 계속 다음 블럭의 크기와 할당여부를 찾다가 block size == 0인 순간 힙 영역의 끝에 도달한거임.

헤더 때문에 최소 블럭 사이즈가 2 워드(8bytes) 가 된다.하나는 헤더, 다른 하나는 정렬 조건을 달성하기 위해서.

9.9.7. Placing Allocated Blocks

9.9.8. Splitting Free Blocks

9.9.9. Getting Additional Heap Memory

9.9.10. Coalescing Free Blocks

9.9.11. Coalescing with Boundary Tags

footer의 도입으로 prev, post free blocks에 대한 병합이 상수 시간 안에 가능해졌다. 다만, 불필요한 메모리 오버헤드가 발생할 우려가 있다. 물론 이전 블럭이 해제되지 않은 경우라면 자기 블럭의 푸터를 사용하지 않는 방식으로 최적화를 도모할 수 있기는 하다. 아니면 아예 요청할 때 버퍼나 메모리 풀 따위를 두어서 큼직큼직하게 받던가

9.9.12. Putting It Together: Implementing a Simple Allocator

malloclab에서 진행한 실습 확인바람.

9.9.13. Explicit Free Lists

Implicit Free Lists 기법은 모든 블럭들을 순회하며 free block을 찾아야 해서 선형시간이 걸린다. 이 시간을 줄이기 위해 free block들의 페이로드 첫 두 바이트를 할애해 각각 predecessor와 successor를 두어 연결리스트로 만들어 버리는 방법이 있다.

하지만 결국 free block을 연결해봤자 선형시간인 건 똑같은데, 최적화 방법은 없을까?

9.9.14. Segregated Free Lists

concept

할당 시간을 줄이는 효과적인 방법으로 블록사이즈를 기준으로 같은 빈(또는 클래스)에 넣어버리는 방법을 분리가용리스트(segregated free list)라고 부른다. 대표적으로 블록사이즈를 2의 지수승에 따라 구분해 보관하게 되면 할당에 필요한 시간을 로그수준으로 줄일 수 있을 것이다.

Simple Segregated Free Lists

Free blocks are never split to satisfy allocatioin requests.

특이하게도, 블록을 쪼개지 않고 해당 빈에 있는 원소의 크기를 통째로 할당한다. => 내부 파편화가 심해질 수 있음.

빈에 원소가 없는 경우, OS에게 빈의 사이즈의 몇배 정도 되는 크기의 공간을 요청하여 빈을 채운 뒤 다시 할당한다. ==> coalesce가 없기 때문에 외부 파편화도 심해진다.

Segregated Fits

segregated free list이기는 한데, split과 coalescing이 가능한 케이스. free blocks를 사이즈에 따라 빈에 담는 건 똑같은데, 이제 새 블럭을 할당할 때 best fit 빈의 첫번째 요소를 찾아 split 후 할당한다. 남은 free block을 적절한 빈에 다시 추가한다.

블럭 해제시 근처 블럭을 병합한 뒤 적절한 빈에 다시 담는다.

Buddy Systems

빈의 크기가 2의 지수승인 Segregated Fits를 Buddy System이라고 부른다. 차이점이라면, Coalescing을 해제할 때가 아닌, 할당할 때 한다는 것이다.